This invention relates generally to broadcasting systems, and more particularly to the scheduling of job requests to be serviced in an on-demand broadcast system.
The demand for broadcast technology has increased with the growth of wireless communication services. Broadcast technology is particularly well suited for disseminating a single item of data to a large number of users.
One type of broadcast system for disseminating information is the push-based system, in which a broadcast server delivers data using a periodic broadcast program based on pre-compiled access profiles and typically without any active user intervention. A broadcast application which transmits or pushes a continuous stream of data relating to stock prices, sports scores or weather forecasts is an example of a push-based system. Push-based systems, however, may not be suitable for dynamic workloads, because the preferences of actual users for a particular data item may differ significantly from the pre-compiled access profiles. In other words, poor performance may result because the scheduling of the data to be disseminated does not account for existing user preferences.
Another type of broadcast system currently being utilized to disseminate data, and the type to which the present invention is directed, is referred to as a pull-based, or xe2x80x9con-demandxe2x80x9d broadcast system. In the on-demand broadcast setting, the server broadcasts information in response to explicit client requests to all users, including those who did not request the information. One example (of many) of an on-demand broadcast system that information. One example (of many) of an on-demand broadcast system that currently exists is one in which users request internet data over phone lines and the broadcast server delivers the data via satellite. Another example is a system which broadcasts news, sports and entertainment updates via a wireless interface and provides live audio or video capability in response to a user""s request.
When explicit client requests are made for the same data items, a broadcast system is used to advantage by satisfying all of the pending job requests for that data item with a single broadcast of the data item. In this manner, a broadcast system is unlike a point-to-point or unicast system, which require that each client""s request for data be individually satisfied, even if more than one client makes a job request for the same data item.
FIG. 1 illustrates a typical on-demand broadcast system. Devices 30a, 30b and 30d make requests for data which are delivered to broadcast server 10 by any uplink method. Specifically, device 30a makes a job request for data item a, device 30b makes a job request for data item b, and device 30d makes a job request for data item d. Broadcast server 10 receives the job requests and broadcasts the requested data via downlink 34 so as to satisfy the job requests. Many job requests may be made for the same data item. Therefore, server 10 may transmit the requested data item once to all of the requesting users at the same time.
Various arrangements for scheduling the broadcast of different data items which have been requested by users have been proposed. One scheduling arrangement, referred to as the xe2x80x9cLongest Wait Firstxe2x80x9d method (hereinafter xe2x80x9cLWF methodxe2x80x9d) examines the total waiting time for all of the pending job requests for specific data items. For example, there may be several job requests to the server for the same data item, each request having arrived at a point in time prior to the present. Furthermore, there may be additional requests to the server for another data item. For each job request, the server calculates the time that has elapsed since the job request arrived until the present. The server then sums all of the elapsed times for job requests for a particular data item. The data item which has the largest summed total of waiting times is serviced first, the data item which has the next largest summed total is serviced second, etc. Another scheduling arrangement which has been proposed is the xe2x80x9cShortest Service Time Firstxe2x80x9d method (hereinafter xe2x80x9cSSTF methodxe2x80x9d), in which the data item which can be transmitted in the least amount of time is serviced first.
Another scheduling method is proposed by D. Aksoy and M. Franklin in xe2x80x9cScheduling for Large Scale On-Demand Data Broadcastxe2x80x9d, March 1998. Generally, this scheduling method utilizes the frequency with which different data items are requested, so as to minimize overall average response time for data items. This method, however, can only be used for homogenous data items. The homogeneity of data items refers to the size of the data item, i.e.xe2x80x94data items are homogenous when they are identically sized. Thus, the scheduling method proposed in this prior art reference does not address heterogeneous data items.
Although the above-referenced scheduling methods for on-demand broadcast systems have attempted to address performance issues, there is an ever increasing need for improved scheduling methods that provide satisfactory performance in terms of worst case response time and overall average response time.
Therefore, there exists a need for a system and method for optimally scheduling the transmission of heterogeneous data items in an on-demand broadcast system.
In accordance with one embodiment of the invention, a method for scheduling responses in an on-demand broadcast system is disclosed. The method comprises the steps of receiving at a broadcast server a plurality of job requests for a plurality of data items, and determining an adaptive schedule for broadcasting the data items. In a departure from prior art scheduling methods for on-demand broadcast systems wherein a response to a job request is transmitted entirely before a following response is transmitted, the schedule in accordance with the present invention is adaptively determined such that the broadcast of a first data item may be interrupted upon receipt of a new job request, so as to broadcast a second data item in accordance with a new schedule, and such that the schedule eliminates job requests for a data item that are pending while the broadcast server broadcasts the requested data item.
In accordance with another embodiment of the invention, an on-demand broadcast server computes a feasible stretch value for use in scheduling heterogeneous job requests to be serviced. A stretch value provides an indication of the delay experienced by each job request to complete, when the server processes many job requests concurrently. In one embodiment, for a set of job requests to be serviced in an off-line setting (to be explained later), a processing time is calculated for each job request based on the size of the job and the bandwidth of the broadcast system. Thereafter, a stretch value is proposed and the broadcast server computes a deadline for each job to be the arrival time of the job request plus the product of the processing time and the proposed stretch value. Thereafter, each job request is scheduled, based on an xe2x80x9cearliest deadline firstxe2x80x9d arrangement, wherein the job request that has the earliest deadline is scheduled first, the job request having the next earliest deadline is scheduled second, etc.
The proposed stretch value is deemed feasible if each pending job request can be completed, if performed in the order determined by the earliest deadline first methodology, prior to its deadline. If the proposed stretch value is deemed not feasible, it is adjusted iteratively until a feasible stretch value is found. Once the feasible stretch value is found, the job requests are serviced in the order dictated by the EDF schedule as found in the latest iteration. Once the broadcast of a job request has been completed, all of the pending job requests for the same data item, which arrived prior to the start of the broadcast, are necessarily simultaneously satisfied and can be eliminated from the pending job requests. According to one embodiment, the feasible stretch value is further adjusted until an optimal feasible stretch value is found, which equals the smallest feasible stretch value which permits, when serviced in the order dictated by the EDF schedule as found in the current iteration, all pending jobs to be completed prior to their deadline.
In another embodiment, job requests are serviced by an on-demand broadcast server in an on-line setting (to be explained later), in which the system services pending job requests prior to determining whether a modified stretch is feasible. In accordance with another embodiment of the invention, the system determines a schedule for a set of pending job requests as a function of all of the job requests from the arrival of the first job request to the system up to the arrival of the current job. In accordance with yet another embodiment of the invention, the system determines a schedule for a set of pending job requests as a function of the last n number of job arrivals, wherein n is an integer.